package nachos.threads;

import nachos.machine.*;

import java.util.*;

/**
 * A scheduler that chooses threads based on their priorities.
 *
 * <p>
 * A priority scheduler associates a priority with each thread. The next thread
 * to be dequeued is always a thread with priority no less than any other
 * waiting thread's priority. Like a round-robin scheduler, the thread that is
 * dequeued is, among all the threads of the same (highest) priority, the
 * thread that has been waiting longest.
 *
 * <p>
 * Essentially, a priority scheduler gives access in a round-robin fassion to
 * all the highest-priority threads, and ignores all other threads. This has
 * the potential to
 * starve a thread if there's always a thread waiting with higher priority.
 *
 * <p>
 * A priority scheduler must partially solve the priority inversion problem; in
 * particular, priority must be donated through locks, and through joins.
 */
public class PriorityScheduler extends Scheduler
{
    /**
     * Allocate a new priority scheduler.
     */
    public PriorityScheduler()
    {
    }

    /**
     * Allocate a new priority thread queue.
     *
     * @param    transferPriority    <tt>true</tt> if this queue should
     * transfer priority from waiting threads
     * to the owning thread.
     * @return a new priority thread queue.
     */
    public ThreadQueue newThreadQueue(boolean transferPriority)
    {
        return new PriorityQueue(transferPriority);
    }

    public int getPriority(KThread thread)
    {
        Lib.assertTrue(Machine.interrupt().disabled());

        return getThreadState(thread).getPriority();
    }

    public int getEffectivePriority(KThread thread)
    {
        Lib.assertTrue(Machine.interrupt().disabled());

        return getThreadState(thread).getEffectivePriority();
    }

    public void setPriority(KThread thread, int priority)
    {
        Lib.assertTrue(Machine.interrupt().disabled());

        Lib.assertTrue(priority >= priorityMinimum &&
                priority <= priorityMaximum);

        getThreadState(thread).setPriority(priority);
    }

    public boolean increasePriority()
    {
        boolean intStatus = Machine.interrupt().disable();

        KThread thread = KThread.currentThread();

        int priority = getPriority(thread);
        if (priority == priorityMaximum)
        {
            Machine.interrupt().restore(intStatus);
            return false;
        }

        setPriority(thread, priority + 1);

        Machine.interrupt().restore(intStatus);
        return true;
    }

    public boolean decreasePriority()
    {
        boolean intStatus = Machine.interrupt().disable();

        KThread thread = KThread.currentThread();

        int priority = getPriority(thread);
        if (priority == priorityMinimum)
        {
            Machine.interrupt().restore(intStatus);
            return false;
        }

        setPriority(thread, priority - 1);

        Machine.interrupt().restore(intStatus);
        return true;
    }

    /**
     * The default priority for a new thread. Do not change this value.
     */
    public static final int priorityDefault = 1;
    /**
     * The minimum priority that a thread can have. Do not change this value.
     */
    public static final int priorityMinimum = 0;
    /**
     * The maximum priority that a thread can have. Do not change this value.
     */
    public static final int priorityMaximum = 7;

    /**
     * Return the scheduling state of the specified thread.
     *
     * @param    thread    the thread whose scheduling state to return.
     * @return the scheduling state of the specified thread.
     */
    protected ThreadState getThreadState(KThread thread)
    {
        if (thread.schedulingState == null)
            thread.schedulingState = new ThreadState(thread);

        return (ThreadState) thread.schedulingState;
    }

    /**
     * A <tt>ThreadQueue</tt> that sorts threads by priority.
     */
    protected class PriorityQueue extends ThreadQueue
    {
        protected ThreadState lockholder = null; //队列头
        protected java.util.PriorityQueue<ThreadState> wait;

        PriorityQueue(boolean transferPriority)
        {
            this.transferPriority = transferPriority;
            wait = new java.util.PriorityQueue<>();
        }


        public void waitForAccess(KThread thread)
        {
            Lib.assertTrue(Machine.interrupt().disabled());
            getThreadState(thread).waitForAccess(this);
        }

        public void acquire(KThread thread)
        {
            Lib.assertTrue(Machine.interrupt().disabled());
            getThreadState(thread).acquire(this);
            lockholder = getThreadState(thread);
            getEffectivePriority(lockholder.thread);
        }

        public KThread nextThread()
        {
            Lib.assertTrue(Machine.interrupt().disabled());
            // implement me
            ThreadState x = pickNextThread();//下一个选择的线程
            if(x == null)//如果为null,则返回null
                return null;
//            if(lockholder != null)
//            {
//                lockholder.acquiredQueues.remove(this);
//                lockholder.getEffectivePriority();
//            }
//            lockholder=x;
            acquire(x.thread);

//            if(x!=null) x.waitQueue=null;

            return x.thread;
        }

        /**
         * Return the next thread that <tt>nextThread()</tt> would return,
         * without modifying the state of this queue.
         *
         * @return the next thread that <tt>nextThread()</tt> would
         * return.
         */
        protected ThreadState pickNextThread()
        {
            // implement me
            return wait.poll();
        }

        public void print()
        {
            Lib.assertTrue(Machine.interrupt().disabled());
            // implement me (if you want)
        }


        public void add(ThreadState state) {
            wait.remove(state);
            wait.add(state);
        }

        public boolean isEmpty() {
            return wait.isEmpty();
        }

        /**
         * <tt>true</tt> if this queue should transfer priority from waiting
         * threads to the owning thread.
         */
        public boolean transferPriority;
    }

    /**
     * The scheduling state of a thread. This should include the thread's
     * priority, its effective priority, any objects it owns, and the queue
     * it's waiting for, if any.
     *
     * @see    KThread#schedulingState
     */
    protected class ThreadState implements Comparable<ThreadState>
    {
        /**
         * Allocate a new <tt>ThreadState</tt> object and associate it with the
         * specified thread.
         *
         * @param    thread    the thread this state belongs to.
         */
        public ThreadState(KThread thread)
        {
            this.thread = thread;
            acquiredQueues =new HashSet<>();
            setPriority(priorityDefault);
            effectivePriority = priority;
        }

        /**
         * Return the priority of the associated thread.
         *
         * @return the priority of the associated thread.
         */
        public int getPriority()
        {
            return priority;
        }

        public int calculateEffectivePriority()
        {
            int res = priority;

            for(PriorityQueue acquired : acquiredQueues)
            {
                //比较acquired中的所有等待队列中的所有线程的优先级
                ThreadState ts = acquired.wait.peek();
                if(ts != null && ts.effectivePriority > res)
                {
                    res = ts.effectivePriority;
                    break;
                }
            }

            res = priority >= res ? priority : res;
            return res;
        }

        /**
         * Return the effective priority of the associated thread.
         *
         * @return the effective priority of the associated thread.
         */
        public int getEffectivePriority()
        {
            if(waitQueue != null && !waitQueue.transferPriority)
                return priority;
            // implement me
            int res = calculateEffectivePriority();

            if(waitQueue!=null && res != effectivePriority)
            {
                (waitQueue).wait.remove(this);
                (waitQueue).wait.add(this);
            }
            effectivePriority = res;
            if(waitQueue!=null && waitQueue.lockholder != null)
                if(waitQueue.lockholder.effectivePriority < res)
                    waitQueue.lockholder.effectivePriority = effectivePriority;
            return res;
        }

        /**
         * Set the priority of the associated thread to the specified value.
         *
         * @param    priority    the new priority.
         */
        public void setPriority(int priority)
        {
            if (this.priority == priority)
                return;

            this.priority = priority;
            effectivePriority = priority;
            if(waitQueue != null && !waitQueue.transferPriority)
                getEffectivePriority();

            // implement me
        }


        public void release(PriorityQueue priorityQueue)
        {
            if (acquiredQueues.remove(priorityQueue)) {
                priorityQueue.lockholder = null;
                getEffectivePriority();
            }
        }

        /**
         * Called when <tt>waitForAccess(thread)</tt> (where <tt>thread</tt> is
         * the associated thread) is invoked on the specified priority queue.
         * The associated thread is therefore waiting for access to the
         * resource guarded by <tt>waitQueue</tt>. This method is only called
         * if the associated thread cannot immediately obtain access.
         *
         * @param    waitQueue    the queue that the associated thread is
         * now waiting on.
         * @see    ThreadQueue#waitForAccess
         */
        public void waitForAccess(PriorityQueue waitQueue)
        {
            // implement me
            Lib.assertTrue(Machine.interrupt().disabled());

//            time=++waitQueue.cnt;

            if(this.waitQueue != waitQueue)
            {
                release(waitQueue);
                this.waitQueue = waitQueue;
                waitQueue.add(this);
                if(waitQueue.lockholder != null)
                    waitQueue.lockholder.getEffectivePriority();
            }
        }

        /**
         * Called when the associated thread has acquired access to whatever is
         * guarded by <tt>waitQueue</tt>. This can occur either as a result of
         * <tt>acquire(thread)</tt> being invoked on <tt>waitQueue</tt> (where
         * <tt>thread</tt> is the associated thread), or as a result of
         * <tt>nextThread()</tt> being invoked on <tt>waitQueue</tt>.
         *
         * @see    ThreadQueue#acquire
         * @see    ThreadQueue#nextThread
         */
        public void acquire(PriorityQueue waitQueue)
        {
            // implement me
            Lib.assertTrue(Machine.interrupt().disabled());
            if(waitQueue.lockholder != null)
                waitQueue.lockholder.release(waitQueue);
            waitQueue.wait.remove(this);//如果这个队列中存在该线程，删除
            waitQueue.lockholder = this;

            acquiredQueues.add(waitQueue);
            this.waitQueue = null;
            getEffectivePriority();

//            Lib.assertTrue(waitQueue.isEmpty());
        }

        /**
         * The thread with which this object is associated.
         */
        protected KThread thread;
        /**
         * The priority of the associated thread.
         */
        protected int priority;

        protected int effectivePriority;
        protected PriorityQueue waitQueue=null; // 该线程等待的队列
        protected HashSet<PriorityQueue> acquiredQueues; // 等待该线程的队列

        public int compareTo(ThreadState ts) {
            return ts.effectivePriority - effectivePriority;
//            return effectivePriority - ts.effectivePriority;
//            if(effectivePriority > ts.effectivePriority)
//                return -1;
//            else if (effectivePriority < ts.effectivePriority)
//                return 1;
//            if(time==ts.time) return 0;
//            return time>ts.time?1:-1;
        }
    }

    public static class PriorityTest implements Runnable
    {
        Lock a=null,b=null;
        int name;
        PriorityTest(Lock A,Lock B,int x)
        {
            a=A;b=B;name=x;
        }
        public void run() {
            System.out.println("Thread "+name+" starts.");
            if(b!=null)
            {
                System.out.println("Thread "+name+" waits for Lock b.");
                b.acquire();
                System.out.println("Thread "+name+" gets Lock b.");
            }
            if(a!=null)
            {
                System.out.println("Thread "+name+" waits for Lock a.");
                a.acquire();
                System.out.println("Thread "+name+" gets Lock a.");
            }
            KThread.yield();
            boolean intStatus = Machine.interrupt().disable();
            System.out.println("Thread "+name+" has priority "+ThreadedKernel.scheduler.getEffectivePriority()+".");
            Machine.interrupt().restore(intStatus);
            KThread.yield();
            if(b!=null) b.release();
            if(a!=null) a.release();
            System.out.println("Thread "+name+" finishs.");

        }
    }

    public static void selfTest()
    {
        System.out.println();
        Lock a=new Lock();
        Lock b=new Lock();

        Queue<KThread> qq=new LinkedList<KThread>();
        for(int i=1;i<=4;i++)
        {
            KThread kk=new KThread(new PriorityTest(null,null,i));
            qq.add(kk);
            kk.setName("Thread-"+i).fork();
        }
        for(int i=5;i<=8;i++)
        {
            KThread kk=new KThread(new PriorityTest(a,null,i));
            qq.add(kk);
            kk.setName("Thread-"+i).fork();
        }
        for(int i=9;i<=11;i++)
        {
            KThread kk=new KThread(new PriorityTest(a,b,i));
            qq.add(kk);
            kk.setName("Thread-"+i).fork();
        }
        Iterator it=qq.iterator();
        int pp=1;
        while(it.hasNext())
        {
            boolean intStatus = Machine.interrupt().disable();
            ThreadedKernel.scheduler.setPriority((KThread)it.next(),pp);
            Machine.interrupt().restore(intStatus);
            pp=pp%6+1;
        }
        KThread.yield();
    }



}


